{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/path-sum-ii\n",
    "\n",
    "\n",
    "Runtime: 6 ms, faster than 5.63% of Java online submissions for Path Sum II.\n",
    "Memory Usage: 41.6 MB, less than 13.46% of Java online submissions for Path Sum II.\n",
    "    \n",
    "    \n",
    "\n",
    "```java\n",
    "import java.util.List;\n",
    "import java.util.ArrayList;\n",
    "\n",
    "class TreeNode {\n",
    "    int val;\n",
    "    TreeNode left;\n",
    "    TreeNode right;\n",
    "\n",
    "    TreeNode() {\n",
    "    }\n",
    "\n",
    "    TreeNode(int val) {\n",
    "        this.val = val;\n",
    "    }\n",
    "\n",
    "    TreeNode(int val, TreeNode left, TreeNode right) {\n",
    "        this.val = val;\n",
    "        this.left = left;\n",
    "        this.right = right;\n",
    "    }\n",
    "}\n",
    "\n",
    "class Solution {\n",
    "    List<List<Integer>> paths;\n",
    "    int targtet;\n",
    "\n",
    "    public List<List<Integer>> pathSum(TreeNode root, int sum) {\n",
    "        this.paths = new ArrayList<List<Integer>>();\n",
    "        this.targtet = sum;\n",
    "\n",
    "        this.travel(root, new ArrayList<Integer>());\n",
    "\n",
    "        return this.paths;\n",
    "    }\n",
    "\n",
    "    public void travel(TreeNode node, List<Integer> l) {\n",
    "        if (node == null) {\n",
    "            return; \n",
    "        } else {\n",
    "            l.add(node.val);\n",
    "            if ((node.left == null) && (node.right == null)) {\n",
    "                if (this.sum(l) == this.targtet) {\n",
    "                    List<Integer> copyOfL = new ArrayList<>();\n",
    "                    copyOfL.addAll(l);\n",
    "                    this.paths.add(copyOfL);\n",
    "                }\n",
    "            }\n",
    "        }\n",
    "        int length = l.size();\n",
    "        this.travel(node.left, l);\n",
    "        l = l.subList(0, length);\n",
    "        this.travel(node.right, l);\n",
    "    }\n",
    "\n",
    "    private int sum(List<Integer> l) {\n",
    "        int v = 0;\n",
    "        for (int i = 0; i < l.size(); i++) {\n",
    "            v += l.get(i);\n",
    "        }\n",
    "        return v;\n",
    "    } \n",
    "\n",
    "    public static void main(String[] args) {\n",
    "        TreeNode root = new TreeNode(0);\n",
    "        root.left = new TreeNode(1);\n",
    "        root.left.left = new TreeNode(1);\n",
    "        root.left.right = new TreeNode(0);\n",
    "        root.right = new TreeNode(2);\n",
    "        root.right.left = new TreeNode(-1);\n",
    "        root.right.right = new TreeNode(0);\n",
    "        List<List<Integer>> r = new Solution().pathSum(root, 1);\n",
    "        System.out.println(r.toString());\n",
    "    }\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Java",
   "language": "java",
   "name": "java"
  },
  "language_info": {
   "codemirror_mode": "java",
   "file_extension": ".jshell",
   "mimetype": "text/x-java-source",
   "name": "Java",
   "pygments_lexer": "java",
   "version": "11.0.11+9-Ubuntu-0ubuntu2.20.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}